package com.zhaopin.theswordreferstooffer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author yin.peide
 * @date 2021-06-29 9:39
 * 面试题41：和为s的两个数字VS和为s的连续正数序列
 *   三种解法：
 *   第一种： O(n2) 最简单的那种，先第一个 跟后面所有匹配 然后第二个跟后面所有匹配，直到找到最终结果
 *   第二种： 利用双指针 ，排序的序列专用，一个指针指向头节点，一个指针指向尾节点，然后看和比S之间的大小决定移动哪个指针
 *   第三种： 也就是下面的解法，放到一个map中，然后看 s-cur 时候在map中，在就拿到了，不在就没获取到
 */
public class Offer41 {
    public static void main(String[] args) {
        int[] attr = {1,3,54,5};
        int[] a = twoSum(attr,57);
        System.out.println(a);
    }

    public static int[] twoSum(int[] numbers, int target) {

        Map<Integer, Integer> map = new HashMap<>();

        for (int cur = 0, tmp; cur < numbers.length; cur++) {
            tmp = numbers[cur];
            if (map.containsKey(target - tmp)) {
                return new int[]{map.get(target - tmp) + 1, cur + 1};
            }
            map.put(tmp, cur);
        }

        throw new RuntimeException("results not exits");

    }

}
